package someTestExcemple.huaweiOd.greedyMethod;
//华为OD机试 - 最短木板长度 - 二分查找（Java 2024 B卷 100分）
//https://blog.csdn.net/guorui_java/article/details/130938829
//找最大化最小值问题 --试一下二分搜索
import java.util.*;
/*一、题目描述
        小明有 n 块木板，第 i ( 1 ≤ i ≤ n ) 块木板长度为 ai。
        小明买了一块长度为 m 的木料，这块木料可以切割成任意块(最小值为1)，拼接到已有的木板上，用来加长木板。
        小明想让最短的木板尽量长。 请问小明加长木板后，最短木板的长度可以为多少？

        二、输入描述
        输入的第一行包含两个正整数，n(1≤n≤103)、m(1≤m≤106)；

        n表示木板数，m表示木板长度。输入的第二行包含n个正整数，a1,a2,…an(1≤ai≤106)。

        三、输出描述
        输出的唯一一行包含一个正整数，表示加长木板后，最短木板的长度最大可以为多少？

        四、测试用例
        测试用例1
        1、输入
        1 10
        5

        2、输出
        15

        3、说明
        只有一块木板，初始长度 5，加上所有 10 的木料可达到 15。

        测试用例2
        1、输入
        4 8
        4 4 4 4

        2、输出
        6*/
public class MinimumLengthOfBoard {
    private static int maxShortestBoard = Integer.MIN_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Integer> boards = new ArrayList<>();
        for(int i=0;i<n;i++) {
           boards.add(sc.nextInt());
        }
        Collections.sort(boards); //按木板长度升序
        //二分查找，寻找最大的最短木板  O(n log n + n log m) 大多数情况通用
        int left = boards.get(0);
        int right = boards.get(0) + m;
        while(left <= right) {
            int mid  = left + (right-left)/2;
            if(canAchive(boards,mid,m)) {
                maxShortestBoard = Math.max(maxShortestBoard,mid);
                //试一下还能不能更大
                left = mid+1;
            } else {
                //小一点看看可不可以
                right = mid-1;
            }
        }
        System.out.println(maxShortestBoard);

    }

    private static boolean canAchive(List<Integer> boards, int target,int totalLen) {
        int totalNeedLen =0;
        for(Integer board : boards) {
            if(board < target) {
                totalNeedLen += target - board;
            }
        }
        return totalNeedLen <= totalLen;
    }

    //方法2 -贪心法（直接模拟分配过程）
    //最短的木板依次期望增长至下一个更长的木板，每次检查剩余长度够不够
    //	O(n log n) 木板长度分布均匀时效率高
    public static int maximizeMinLengthGreedy(int n, int m, int[] a) {
        Arrays.sort(a);
        int currentMin = a[0];
        int remaining = m;

        for (int i = 1; i < n && remaining > 0; i++) {
            int diff = a[i] - a[i - 1];
            if (diff > 0) {
                //todo 精髓啊 如果i=2，就是说第0，1号木板长度都为1号木板了，此时
                //期望增长值2号木板 需要的长度是diff*i;
                int needed = diff * i;
                if (remaining >= needed) {
                    remaining -= needed;
                    currentMin = a[i];
                } else {
                    //如果剩下长度不够第0-i-1号木板都增长至i号木板
                    //就把剩下这点给最短的均分掉
                    currentMin += remaining / i;
                    remaining = 0;
                    break;
                }
            }
        }
        //这种是n块版一样长的情况
        if (remaining > 0) {
            currentMin += remaining / n;
        }

        return currentMin;
    }
}
